package jm.algorithm.sort;

/**
 * @Description 归并排序
 * @date 2022/5/4 7:50
 */
@SuppressWarnings("unchecked")
public class MergeSort<T extends Comparable<T>> extends Sort<T> {

    // 左侧数组
    private T[] leftArr;

    @Override
    protected void sort() {
        // 左侧数组最大长度为 length / 2
        leftArr =  (T[])new Comparable[arr.length >> 1];
        sort(0,arr.length);
    }

    /**
     * 对 [being,end) 范围内数据进行归并排序
     * @param begin
     * @param end
     */
    private void sort(int begin, int end){
        if (end - begin < 2) return; // 元素数量小于 2 不需要进行分割
        // 从中间分割
        int mid = (begin + end) >> 1;
        // 左侧递归分割
        sort(begin,mid);
        // 右侧递归分割
        sort(mid,end);
        merge(begin,mid,end);
    }

    /**
     * 将 [begin,mid) 和 [mid, end) 的 序列 合并成一个一个有序序列
     * @param begin
     * @param mid
     * @param end
     */
    private void merge(int begin, int mid, int end){
        // 左侧开始li ，左侧最后元素 arr[mid - begin - 1]
        int li = 0, le = mid - begin;
        // 右侧开始ri ，右侧最后元素arr[end - 1]
        int ri = mid, re = end;
        // 目标覆盖位置
        int ai = begin;

        // 备份左侧数据到leftArr
        // 因为这里合并的是 begin 到 end 之间的，在除第一个分割外begin都不是0 ，所以备份时应该使用 begin + i。
        for (int i = li; i < le; i++) {
            leftArr[i] = arr[begin + i];
        }

        while (li < le){ // 不符合就表示左侧数组进入到右侧结束，不需要再进行任何操作。
            if (ri < re && cmp(arr[ri],leftArr[li]) < 0){ // 保证右侧没有结束，将小的放入到数组中
                arr[ai] = arr[ri];
                ri++;
                ai++;
            }else { // 如果右侧结束 或者 左侧值大于右侧值 将左侧元素放入数组中
                arr[ai] = leftArr[li];
                li++;
                ai++;
            }
        }
    }
}
